#include <stdio.h>
#include <string.h>

typedef char node;
#define key(A) (A)
#define exch(A, B) { node t = A; A = B; B = t; }

void fixup(node *, int k);
void fixdown(node *, int k, int n);
void heap_sort(node a[], int l, int r);

int main()
{
  node v[256]; strcpy(v, "HEAPSORT");
  int n = strlen(v);
  heap_sort(v, 0, n);  
  //int i; for (i = 0; i < n; i++)  printf("%c", v[i]);
  return 0;
}

void fixup(node a[], int k)
{
  while (k > 1 && key(a[k/2]) < key(a[k])) {
    exch(a[k], a[k/2]);
    k = k/2;
  }
}

void fixdown(node a[], int k, int n)
{
  while (2*k <= n) {
    int j;
    j = 2*k;
    if (j < n && key(a[j]) < key(a[j+1])) j++;
    if (!(key(a[k]) < key(a[j]))) break;
    exch(a[k], a[j]);
    k = j;
  }
} 

void heap_sort(node a[], int l, int r)
{
  int k, n = r-l+1;
  node *pq = a+l-1;
  for (k = n/2; k >= 1; k--) fixdown(pq, k, n);
  while(n > 1) {
    exch(pq[l], pq[n]);
    fixdown(pq, l, --n);
  }
}

